基数排序（Radix Sort）是一种非比较排序算法，它通过将数字按位数切割成不同的数字，然后按每个位数分别比较来实现排序。这种排序算法需要保证被排序的数据可以分割成独立的位数，然后按位数递增或递减的顺序进行排序。

- 以下是基数排序的基本思路：

  - 找到数组中最大数的位数，用于确定排序的轮数；
  - 从最低位开始，按照位数的大小，对所有数字进行一次排序；
  - 重复第二步，直到所有位数都被排序。

- 举个例子，假设有一个数组 [53, 3, 542, 748, 14, 214, 154, 63, 616]，我们可以按照以下步骤对其进行排序：
  - 找到数组中最大数 748 的位数，即三位数，因此需要进行三轮排序；
  - 第一轮排序按照个位数进行排序，排序结果为 [542, 53, 63, 3, 616, 154, 14, 748, 214]；
  - 第二轮排序按照十位数进行排序，排序结果为 [3, 14, 214, 616, 748, 53, 542, 63, 154]；
  - 第三轮排序按照百位数进行排序，排序结果为 [3, 14, 53, 63, 154, 214, 542, 616, 748]；
  - 数组已经排序完成。

```js
function radixSort(arr) {
  // 获取数组中最大的数，并计算其位数
  const maxNum = Math.max(...arr);
  const maxDigits = String(maxNum).length;

  // 对每一位进行排序
  for (let i = 0; i < maxDigits; i++) {
    // 初始化桶
    const buckets = Array.from({ length: 10 }, () => []);

    // 将数组元素分配到桶中
    for (let j = 0; j < arr.length; j++) {
      const digit = getDigit(arr[j], i);
      buckets[digit].push(arr[j]);
    }

    // 将桶中的元素合并为一个数组
    arr = [].concat(...buckets);
  }

  return arr;
}

// 获取数字 num 在 d 位上的数字
function getDigit(num, d) {
  return Math.floor(Math.abs(num) / Math.pow(10, d)) % 10;
}
```

- 在上述代码中，基数排序算法的实现分为以下几个步骤：
    - 首先获取数组中的最大数和最大位数，用于决定排序的轮数。
    - 对于每一轮排序，根据当前位数将数组元素分配到相应的桶中。
    - 将每个桶中的元素按顺序合并为一个数组，作为下一轮排序的输入。
    - 重复第2步和第3步，直到所有的位数都已经处理完毕。
在这个实现中，我们使用 getDigit() 函数获取数字在指定位数上的数字，并使用 Array.from() 和扩展运算符（...）来创建和合并桶数组。


:::info
基数排序的时间复杂度为 O(nk)，其中 n 是排序的数字个数，k 是数字的最大位数。虽然基数排序的时间复杂度相对较小，但是由于其需要额外的存储空间，因此在实际应用中并不常用。
:::
